/**
 * Author: 笨蛋超人不会飞
 * Date:  15:05
 */
public class question_121 {
}
//买卖股票的最佳时机
class Solution_121 {
    public int maxProfit(int[] prices) {
//        解法一：暴力算法，采用双层for循环，但是这样时间复杂度为n^2，会多一些重复的计算
//        int max_profit=0;
//        for (int i = 0; i < prices.length-1; i++) {
//            for (int j = i+1; j < prices.length; j++) {
//                if (prices[j]-prices[i]>max_profit){
//                    max_profit=prices[j]-prices[i];
//                }
//            }
//
//        }
//        return max_profit;
//

//        解法二：采用单层的for循环
//        动态规划的思想
        if(prices==null||prices.length==0){
            return 0;
        }
//        设置购入的最小价格，先定义一个无穷大的值
        int min_price=1000000;
        int max_profit=0;
        for (int i = 0; i <prices.length; i++) {
            if(prices[i]<min_price){
                min_price=prices[i];
            }else {
//                这样的话对于每一个prices[i]来说，min_price都是在它前面的最低的购入价格
                if(max_profit<prices[i]-min_price){
                    max_profit=prices[i]-min_price;
                }
            }
        }
        return max_profit;
    }
}
